import com.company.Solution205;

public class Solution85 {
    public int maximalRectangle(char[][] matrix) {
        if (matrix.length==0){
            return 0;
        }
        int[][] helpMatrix=new int[matrix.length][matrix[0].length];
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if(matrix[i][j]=='0'){
                    helpMatrix[i][j]=0;
                    continue;
                }
                if(j-1>=0){
                    helpMatrix[i][j]=helpMatrix[i][j-1]+1;
                    continue;
                }
                helpMatrix[i][j]=1;
            }
        }
        int maxArea=0;
        for (int i = matrix[0].length-1; i >=0 ; i--) {
            for (int j = matrix.length-1; j >=0 ; j--) {
                int minLen=helpMatrix[j][i];
                for (int k= j; k>=0 ; k--) {
                    if (helpMatrix[k][i]==0){
                        break;
                    }
                    if (helpMatrix[k][i]<minLen){
                        minLen=helpMatrix[k][i];
                    }
                    int tempArea=minLen*(j-k+1);
                    if(maxArea<tempArea){
                        maxArea=tempArea;
                    }
                }
            }
        }
        return maxArea;
    }

    public static void main(String[] args) {
        Solution85 s=new Solution85();
        System.out.println(s.maximalRectangle(new char[][]{{'1','0','1','0','0'},{'1','0','1','1','1'},{'1','1','1','1','1'},{'1','0','0','1','0'}}));

    }
}
